Khi những người lính cuối cùng của Napoléon Bonaparte rời Moskva, Sa hoàng Aleksandr I đã ký một bản tuyên ngôn, 25 tháng 12 năm 1812, tuyên bố sự lưu tâm của mình để xây dựng một nhà thờ lớn để tôn kính Chúa cứu thế "nhằm biểu hiện sự biết ơn của chúng ta đến Thượng đế tiên đoán cho việc cứu giúp nước Nga khỏi sự tàn phá đã che bóng nó" và để tưởng nhớ đến những hy sinh của người Nga.

Phải đến một thời gian sau, người ta mới bắt tay vào thiết kế và xây dựng nhà thờ. Đồ án kiến trúc cuối cùng được tán thành bởi Aleksandr I năm 1817. Đó là một thiết kế tân cổ điển mang nhiều dấu ấn và biểu tượng của Hội kín Freemason. Công việc xây dựng được bắt đầu trên Đồi chim sẻ, điểm cao nhất ở Moskva, nhưng chỗ này lại tỏ ra là không an toàn.

Trong khi đó, em trai của Aleksandr I là Nikolai I lên ngôi. Là một người theo chủ nghĩa ái quốc và là tín đồ trung thành của Chính thống giáo, Sa hoàng mới không tỏ ra thích thú với các trường phái Tân cổ điển và Freemason trong đề án được chấp thuận bởi anh trai mình. Ông ta ủy nhiệm kiến trúc sư ưa thích của mình, Konstantin Thon để vẽ ra một thiết kế mới, lấy mẫu từ nhà thờ Hagia Sophia ở Constantinople. Thiết kế theo trường phái Tân Byzantine của Thon được phê chuẩn năm 1832, và một địa điểm mới, gần với Điện Kremli hơn, được lựa chọn bởi Sa hoàng vào năm 1837. Một chủng viện và nhà thờ tại đó phải được chuyển đi, vì vậy viên đá góc không được đặt cho đến năm 1839.